Information transmitted over a communication channel is generally received as a combination of the original information and a noise component. Integrity of the information content is substantially entirely preserved when the signal to noise ratio of the system is large. Accordingly, refinements in design and realization of the appropriate hardware can increase the probability or error-free transmission, theoretically, up to the limits imposed by the channel itself. In order to minimize the effect of intrinsic channel limitations, various techniques are employed which ultimately require a compromise between bandwidth and information transfer rate. Various limitations imposed on the channel bandwidth, information rate, and the degree of complexity of receiving and transmitting apparatus contribute to a probable error rate.
Although redundancy is a common element among these techniques, mere repetition exacts a heavy penalty in transmission rate. For example, a single repetition reduces the information rate 50% and a second repetition (to implement majority logic) reduces the information rate by 611/2%. Other means for insuring message integrity have employed sophisticated coding techniques which permit the detection, location, and correction of errors. Among the desiderata of these coding techniques are high information rate and a capability of correcting multiple errors within any given codeword of transmitted data.
In this context a codeword results from encoding operations performed upon the elements of the original data comprising k bits to yield an encoded word ("codeword") of information having k information bits and r check bits. The encoded redundancy in the form of r check bits is then available during the decoding operations to detect and correct errors in the codeword (including all k+r bits) up to some limit or merely to detect errors up to some larger limit.
Many such codes, having distinct mathematical properties, have been studied and mathematically efficient decoding procedures have been devised, but reduction to practice with concomitant efficiency requires a special purpose computer. For example, certain classes of codes are founded on association of each information element of a codeword with an element of a Galois field.
Very briefly, the Galois field is a finite field, the elements of which may be represented as polynomials in a particular primitive field element, with coefficients in the prime subfield. The locations of errors and the true value of the erroneous information elements are determined after constructing certain polynomials defined on the Galois field and finding the roots of these polynomials. A decoder is therefore required which has the capability of performing Galois field arithmetic.
Of the error correcting codes, a particular class of such codes, separately described by Bose, Chaudhuri and Hocquenhem (thus "BCH" codes), are capable of multiple error correction. A special case of such codes are the Reed-Solomon (RS) Codes with respect to which the present invention will be described.
One approach to the problem of sufficiently high speed error correction of BCH encoded data was described in terms of an algorithm published in my text "Algebraic Coding Theory" (McGraw-Hill, 1968). Prior art employment of the aforesaid algorithm has utilized in one instance a general purpose digital computer controlling an essentially peripheral arithmetic unit implementing Galois field manipulation. Certain prior art arithmetic units have used large stored tables to implement inversions appearing in decoding procedures.
Other prior art Galois field arithmetic units employ iterative multiplications for inversions, thereby avoiding heavy penalties in hardware and calculation time, which are associated with division operations. Finite field multiplication manipulation can lead to inversion because in a Galois field, as for example, the field GF(2.sup.5), EQU beta.sup.31 =Beta.sup.0 =1.
Consequently EQU beta.sup.30 =beta.sup.-1
Thus, given a quantity beta, a straightforward prior art method of obtaining its inverse, beta.sup.-1 is defined by performing 2.sup.m -2 (here 30) repetitions of a Galois field multiplication upon the Galois field representation of beta in the Galois field GF (2.sup.m).
Prior art computers have conventionally employed memory addressing techniques based on an arithmetically sequential organization of information. Addressing is physically implemented by developing an effective address which may be the result of conventional arithmetic operations. Address modification is conventionally effected in hardware which performs an addition or decremention of a base address. Consequently, circuitry implementing this conventional form of address modification incorporates adder circuits to arithmetically increment or decrement an address with a resulting delay for signal propagation corresponding to the arithmetic carry operation between adjacent bit positions of a working register wherein the result is developed.